package club.xiaojiawei.dp;

import java.util.Arrays;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/23/22 12:11 AM
 * @question 132. 分割回文串 II
 * @description 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
 * 返回符合要求的 最少分割次数 。
 */
public class MinCut132 {

    public static void main(String[] args) {
        MinCut132 test = new MinCut132();
        int result = test.minCut("ab");
        System.out.println(result);
    }

    /**
     * 官方-dp
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(n^2)
     * @param s
     * @return
     */
    public int minCut(String s) {
        int n = s.length();
//        预处理：g[i][j]表示i到j是否为回文子串
        boolean[][] g = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(g[i], true);
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                g[i][j] = s.charAt(i) == s.charAt(j) && g[i + 1][j - 1];
            }
        }

//        f[i] = n 表示0到i最小切割n次
        int[] f = new int[n];
        Arrays.fill(f, Integer.MAX_VALUE);
        for (int i = 0; i < n; ++i) {
            if (g[0][i]) {
                f[i] = 0;
            } else {
                for (int j = 0; j < i; ++j) {
                    if (g[j + 1][i]) {
                        f[i] = Math.min(f[i], f[j] + 1);
                    }
                }
            }
        }

        return f[n - 1];
    }

    /**
     * 民间-dp（nb）
     * @param s
     * @return
     */
    public int minCut2(String s) {
        int length = s.length();
        if (length == 1) {
            return 0;
        }
        int[] dp = new int[length];
        //赋初值，最多的情况是按单个字符切分, cut[0]设为-1
        for (int i = 0; i < length; i++){
            dp[i] = i;
        }
        char[] chars = s.toCharArray();
        for (int i = 0; i < length; i++) {
            findMin(chars, i, i, dp);
            findMin(chars, i, i + 1, dp);
        }
        return dp[length - 1];
    }
    public void findMin(char[] chars, int i, int j, int[] dp){
        while (i >= 0 && j < chars.length && chars[i] == chars[j]){
            dp[j] = Math.min(dp[j], i == 0? 0 : dp[i - 1] + 1);
            i--;
            j++;
        }
    }
}
